#ifndef lint
#ifdef __GNUC__
#define ATTRIBUTE(attrs) __attribute__(attrs)
#else
#define ATTRIBUTE(attrs)
#endif
static char Rcs_Id[] ATTRIBUTE((used)) =
    "$Id: mtcctest.cc,v 1.7 2012-12-30 16:24:49-08 geoff Exp $";
#endif

/*
 * Test the C++ version of the Mersenne Twister PRNG
 *
 * $Log: mtcctest.cc,v $
 * Revision 1.7  2012-12-30 16:24:49-08  geoff
 * Use gcc attributes to suppress warnings on Rcs_Id.
 *
 * Revision 1.6  2010-06-24 01:45:46-07  geoff
 * Move volatile declarations to the top of the function to ensure they
 * are effective.
 *
 * Revision 1.5  2007-10-26 00:21:06-07  geoff
 * Don't throw away random values in the timing tests, since then the
 * compiler would optimize the entire loop away.
 *
 * Revision 1.4  2003/09/11 05:50:53  geoff
 * Use the standard namespace.  Get rid of a troublesome setbuf call that
 * I'm too lazy to figure out how to get to work.
 *
 * Revision 1.3  2001/06/19 00:41:16  geoff
 * Put a newline after the saved data, now that the type doesn't.
 *
 * Revision 1.2  2001/06/18 05:40:11  geoff
 * Do 300 million timing loops by default.
 *
 * Revision 1.1  2001/06/14 10:52:29  geoff
 * Initial revision
 *
 */

#include "mtwist.h"
#include <fstream>
#include <iomanip>
#include <iostream>
#include <unistd.h>
#include <stdlib.h>
#include <sys/resource.h>
#include <sys/time.h>

using namespace std;

int		main (int argc, char * argv[]);
static void	report_timing(long loops, struct rusage * then);

/*
 * Base unit for timing loops, so the caller can think in millions.
 */
#define TIMING_LOOP_BASE	1000000

/*
 * Default number of timing loops to do
 */
#define TIMING_LOOPS		(300 * TIMING_LOOP_BASE)

/*
 * The following table contains values that were generated by Matsumoto and
 * Nishimura's C program for the Mersenne Twist algorithm, using the
 * default seed of 4357.  These values are presumed to be correct.  The
 * test program compares the values generated by this implementation with
 * the reference values to ensure that the generator has been implemented
 * correctly.
 */
static unsigned long	correct_values[] =
    {
    3510405877u, 4290933890u, 2191955339u,  564929546u,  152112058u,
    4262624192u, 2687398418u,  268830360u, 1763988213u,  578848526u,
    4212814465u, 3596577449u, 4146913070u,  950422373u, 1908844540u,
    1452005258u, 3029421110u,  142578355u, 1583761762u, 1816660702u,
    2530498888u, 1339965000u, 3874409922u, 3044234909u, 1962617717u,
    2324289180u,  310281170u,  981016607u,  908202274u, 3371937721u,
    2244849493u,  675678546u, 3196822098u, 1040470160u, 3059612017u,
    3055400130u, 2826830282u, 2884538137u, 3090587696u, 2262235068u,
    3506294894u, 2080537739u, 1636797501u, 4292933080u, 2037904983u,
    2465694618u, 1249751105u,   30084166u,  112252926u, 1333718913u,
     880414402u,  334691897u, 3337628481u,   17084333u, 1070118630u,
    2111543209u, 1129029736u, 2769716594u,  198749844u, 2123740404u,
    3372116884u,  667945179u, 1235233343u, 1413475797u, 2355129622u,
    3131889314u, 1361507145u, 3419810344u, 3753862504u, 2643520359u,
     854777807u, 2823672895u, 1563137348u, 2778071293u, 3360232580u,
    1294979669u, 2667002587u, 4095439979u,  806669383u, 3717814038u,
    1071953403u, 3630859637u,  771361748u, 1131385020u, 3697612515u,
    4264844916u, 1364828348u, 2863894246u, 1109863328u, 3066937191u,
    2778683115u, 3989613953u,  859474495u,  167522376u, 1094225558u,
    1963711766u, 1257324636u, 1729949323u,  125753755u, 1068698284u,
    1761594045u, 2106609220u, 1033190229u,  946183933u, 1100436279u,
     489306665u, 2385045156u,  658699819u, 3308017340u, 2385997510u,
     105622857u, 1976233741u, 1535497010u,  314176889u, 1247500738u,
    2138106664u, 2757078771u, 2433460811u, 3970906471u, 1944201130u,
    2366336502u, 2541539915u, 4284982935u,  224898482u, 1457988276u,
    2188154237u, 3655119144u,  979144237u, 1279857832u, 2711710163u,
    4093937260u, 2299893420u, 2121869254u, 2505459837u, 1847263294u,
    2974457633u, 3439803738u, 1672773492u,  225684598u, 2496857387u,
     611619631u, 3993022877u, 3508398016u, 1663733971u,  758566080u,
    1653863133u, 1701066037u, 3782883361u, 3343813716u, 2602577666u,
     629577870u, 3724093470u,  361301181u, 2674434977u, 1443899064u,
    4104796692u,  140754167u, 4230942998u,  447458027u,  743917836u,
    2818315151u, 1332110941u,  266033703u,  308176090u,  130356650u,
    3074197472u, 3093392044u, 1602712035u, 1856287253u, 3375970245u,
    3114872063u,  370413632u, 1435286098u,  645351481u,  908917276u,
    2440368438u, 1599412846u, 2500100729u,  790131292u, 3684521490u,
    4052663936u, 1566488352u,  295035953u, 4163443199u, 2997925650u,
     678068969u, 3667661122u, 1273385972u, 3555794914u,  762012623u,
    1091375739u, 1765680277u, 4238179361u, 3406590822u, 3797246256u,
     388618876u, 2160693563u,  349961032u, 1392360403u, 3579025090u,
     604490212u, 3577823930u, 2321462651u, 3790422055u, 3185735941u,
    2229660586u, 1128575466u,  884862908u, 3330757128u, 3194168238u,
     681073659u,  800341641u, 2006864675u, 2619636221u, 1577889182u,
    3575155952u, 2260116784u, 3689141878u, 1657848984u, 2642380231u,
    2878484564u, 3099953080u,  468844464u, 4134363631u, 4110639840u,
    1904558184u, 1937194892u, 3137602491u, 3643695698u,  820242909u,
    3068372731u, 3388748923u, 4235603065u, 2615115373u, 1555770904u,
    1520951990u, 1047053830u, 1663094463u, 3948465044u, 1077597088u,
    2996944317u, 3230974609u, 2019388652u,  865275198u, 2046271241u,
    3163620630u,  269072378u, 2253440754u,  277763586u, 1114595358u,
    2679817222u,  988885471u,  922982460u,  477046426u, 1161679484u,
    2950091998u, 2088879880u, 3516906501u, 1403601752u, 1184069822u,
    3531029460u, 3041313352u, 3359174170u, 2117925252u, 1529768389u,
    1253051929u, 1829668776u, 2678766355u, 2138924913u, 3147299808u,
     447212163u, 1069119222u, 3791704659u,  804904386u, 3580345412u,
    1700215583u,  904016717u,   74539975u, 1288558083u, 1746888271u,
     437611701u,  781576281u, 1166365552u, 2566333668u, 4292856916u,
    4076802480u, 3968908047u, 3057346051u, 2074623641u, 3653637364u,
     586217310u, 3211306229u, 2604443978u, 3303224219u,   50953535u,
    2118693299u,  460196852u, 3355264342u,  500727351u, 1681849672u,
     113995187u, 1200937601u, 3092561862u,  312936130u, 3916083024u,
    2561711416u, 3713941700u, 2240434908u,  637144400u, 1946468041u,
    3224254139u, 2242555323u, 2524984519u,  945834669u, 2805199117u,
    1879274691u, 3792160120u,   37879558u, 1205870756u, 3508020184u,
    2705733735u, 3134213377u, 3170077556u,    9055729u, 2147895752u,
    3788046325u, 2422273092u, 1228026268u, 1275162816u, 1385450594u,
     128490357u,  678715088u, 2466464403u, 2715463741u,  420067866u,
     396072989u, 1729810791u, 4146068843u,  389936193u, 1010939382u,
     794725144u,  633726173u, 3567793282u,  248988111u, 1254549356u,
    1989964616u, 1425389196u, 2202358947u, 2830413406u, 3798927382u,
    3442966168u,  269966252u, 2807646342u, 1794971636u, 1602977220u,
    1360381486u, 1805272988u,  554730358u, 4259897540u, 2168740091u,
     442942697u, 3744617621u, 3567326073u, 1232342342u, 3720210842u,
     303505483u, 3533762586u, 2136482547u, 2813945830u, 3051833277u,
    2830164695u, 3157472512u, 3186113013u, 1063305342u, 4133844231u,
    2026873438u,   94687021u,   42670911u, 2205451721u,  200274097u,
    3184342380u, 1216199867u, 1941807482u, 1902652464u, 4140258655u,
    1934749011u, 2626251395u, 1041046135u, 3256560316u, 2005577300u,
     367040511u, 2562291571u, 4179257085u,  394550850u, 3714400922u,
    3096861476u, 3729796880u, 3528309113u, 1483426196u,  821348673u,
    2057501468u, 3141389956u,  631596202u, 2325651773u, 3568751628u,
    2300178836u,  257777076u, 3455675689u, 2853908813u,  223950412u,
    2320715588u,  250378269u, 3557833937u,  927098460u,  315421373u,
    1957400381u,  725633141u, 3345409284u, 1114863797u, 1830809043u,
    1922707457u, 3785762071u, 3404751487u, 2434832700u, 1359584120u,
     860423718u, 2979956529u,  888063953u,  641814761u,  180527770u,
    3316862637u, 4012959929u,   28566252u, 1045558574u, 4131606737u,
     215968520u,  362234156u, 2248115936u, 3069089212u, 3403600809u,
    1812984601u, 1768934064u, 4007586160u, 1240758160u,   13887765u,
    3514615109u, 3827374039u, 3341198715u, 1982839159u, 2033151304u,
    4283902822u, 3744190534u,  726223056u, 3905246635u, 1875803225u,
    2030522753u, 2822074688u, 3325482280u, 1691268105u, 3033866845u,
    1716543028u, 1555574049u, 2661093496u, 1979855811u, 2251933935u,
    1276056752u, 3341241268u, 1892612984u, 2194846054u,  486586963u,
    2492823590u,  593230942u,  775986230u, 1255789287u, 2318099602u,
    3056263080u,  158332807u, 2451929550u, 3374135491u,  372847709u,
    1128359579u,  373993639u, 2419119952u,  829613207u, 2948211163u,
    2324165819u,  160722663u, 1444930279u,  765460462u, 3780495422u,
     592264489u,  316670611u, 2342138965u, 1439591408u, 3362218290u,
    2860902653u, 1116562887u, 3033679152u, 1381679779u, 1291533463u,
    1962666710u, 2222373514u, 1215751045u, 3569236064u, 1611254503u,
    1171727980u, 3057484484u, 3263787664u, 3065712276u,  781477153u,
    1881176626u, 3769042770u, 1193467712u, 2843905090u, 3437666358u,
    2160717604u,  419274206u, 2767079897u, 4007363510u, 1325555048u,
    4187736634u, 4066907010u, 3299749742u,  154249616u, 1941800223u,
    1157563946u,  705258893u,  860757803u, 1310317854u, 1898329708u,
    3491229573u,  312822728u, 3407001878u, 1029352733u, 3463910352u,
    2741163037u, 2705583812u, 2644345635u,  683012156u,  948328240u,
    2656867161u, 1644147624u, 2853875853u,  822059867u,  753937406u,
    1604103884u, 1756360543u, 3400647193u, 2802766030u, 2268191056u,
    3784643944u, 3009927237u,  394432056u, 1840177440u, 2651765924u,
    1205254585u, 3551482241u, 2857937506u, 2522509113u, 3675764066u,
    1234994787u, 3459183960u,  186529857u, 1329960799u, 2322397450u,
    1078548606u,  113242357u, 2421327506u, 3306100881u,  211880652u,
     847202265u, 1034020264u, 2374075486u,  755993425u, 2474409905u,
    1885945103u, 3588026819u, 3326201431u,  747273957u, 3172561912u,
    4064603659u, 2036147813u, 3539583488u, 2861164857u, 3303878586u,
    2385840167u,  734771685u,  804646316u, 1158163327u, 2080435695u,
    2455811362u, 2060318701u, 1223319334u, 2573853731u, 3341336861u,
    3207344772u, 1654544724u, 1227774824u, 1779567885u, 4241425455u,
    3942578957u, 2787959909u,   90390016u, 1235487669u, 2405269696u,
    4096898260u, 2121644059u, 2432007152u, 2649006803u,  355642145u,
    3998121079u, 3524581383u,  919279000u,  789586853u, 2465492036u,
     220701650u, 2947224279u, 1329892616u, 3729919501u, 1219039514u,
    3006882189u,  281458735u, 3800499491u,  730882493u, 2222118351u,
    4107301035u, 2687550208u, 3260886108u, 3701859392u, 3862191362u,
    1412535194u, 1694757183u,  772470279u,  689128388u, 2265554314u,
    3499902942u, 2845535450u, 2570802968u, 1947307958u, 4027367903u,
    1910806179u, 3858889779u, 4021735452u, 4078787932u, 3413032217u,
    2980053565u, 2148809521u, 1497338125u, 2040525958u, 3112062074u,
    2201881275u, 3672285015u, 3003099464u, 3809697025u, 3709177038u,
    3264926503u, 1707537043u, 1104985157u, 3691862420u, 1898692192u,
    2323051094u,  736562662u, 2300313916u, 3100486674u,  302436891u,
    1288467611u, 1981059467u, 3645778636u, 1609399619u, 3418162375u,
    3667843152u,  536318325u, 3040655354u, 2544467931u,  424476355u,
    1601741596u,  246832728u, 2677287644u, 2835422307u, 1127786001u,
     850991343u, 2067806155u, 3766212150u, 1001927094u, 3801068881u,
    3242308737u, 1560596676u, 1681618985u, 2562998394u, 3484825522u,
    2655391996u, 1746361319u, 3550836123u, 4038742826u,  735255465u,
    3954076606u, 4101370050u, 3167012089u, 1966689481u, 1576556523u,
     207036082u, 2337346669u, 3404885158u, 3372194402u, 2313772874u,
    1511011541u, 3934253759u,  152017013u, 2305096656u, 1003233114u,
    3788182044u, 2738083629u, 2667318735u, 4075851512u, 3919952624u,
    3934687504u,  955697805u, 3721361893u, 1892740917u, 1925356403u,
    3530645689u,   57355987u,  500963211u, 3812263275u, 3120702996u,
    3348394440u, 2648242605u, 2950965560u, 2906248872u, 4195607563u,
    1976120064u,  569029796u, 3204894397u,  836657553u, 4253104557u,
    4029524248u, 1167446730u, 3164256694u, 1225943621u,  978942573u,
    3887954057u, 4029693733u, 3371611138u, 2648127182u,  341670719u,
     780349063u, 1249088385u, 2825987206u, 1409751402u, 3493141543u,
    2454446995u, 3001899542u,  894695004u, 4113594037u, 2748119359u,
    3811278462u,  337072564u, 3551268535u, 4210316453u, 2857304716u,
    1656016234u, 3055850193u, 4074141119u, 2702683976u, 3903520288u,
    2708109896u, 1303194166u,  676764765u,    1073839u, 3417024471u,
     530027902u,  664548902u, 3934189521u, 1118172394u, 1598501076u,
    1353136139u, 3556356767u, 3851436279u,  787984702u, 3614996657u,
    2653843342u,  350845053u, 2540767452u,  341795141u, 4131579558u,
    2852231303u,  347703279u,  304754275u, 3637218358u, 1191420956u,
    4250273882u, 2217329477u, 3619012484u, 2320390083u, 1618600250u,
     100602741u, 3962829626u, 3325838530u, 3310041575u, 2202357234u,
    2410265700u, 1855854724u, 1586666379u, 1893433651u, 4212894970u,
    3078470962u, 3005791950u, 3645097109u, 2729330720u,  178175659u,
    1878759843u, 3613064024u, 2235022317u, 1229007963u, 1217716121u,
    3424643385u, 2025817426u, 2541310454u, 3491127040u,  834075061u,
    1476080952u,  527792572u, 3142617040u,  990164480u, 3538861805u,
    1101804820u,  254185979u, 2139277356u, 3053978085u, 3636278570u,
    1588526078u, 3265686058u, 3200724466u, 3305433961u, 1714292212u,
    2894641386u,  286242900u, 2390694965u, 1104137642u, 1729447649u,
    2603147116u, 1739535876u, 2332325654u, 3923517970u,  975963350u,
    3046750553u, 4287139816u, 2887426453u, 3205373337u, 2829120066u,
    3989557087u, 1090404329u, 2762938959u, 2016187695u,  188074317u,
     562585328u, 1185556641u, 3980179851u, 2922039667u, 3215853289u,
     946979886u, 2822925104u,  803185936u, 1852384677u, 2297156223u,
    2799487985u, 1756284627u, 2317738144u, 1335401093u,  674337096u,
    2899555797u, 3996541014u, 3014749938u,  283034558u, 3481962136u,
    3810308241u, 2725662577u,  744192370u, 3665583468u,  571653166u,
    3181462357u, 1782231829u,  563269281u, 1274600369u, 2386970918u,
     363976120u, 2931953430u,  614822572u, 1661454733u,  449226294u,
    3506516244u, 3427050773u, 2620464687u,  505585754u, 3256549852u,
     321182353u, 3890429063u, 2030404657u, 1191957414u, 3469037079u,
     947528907u,  578915297u, 2155016115u,  557136361u,  374100253u,
    1716551606u, 1064892772u, 2282836509u, 2205887435u,  735861059u,
    2088833463u, 3884993958u, 1520195389u, 3349226581u, 4116948321u,
    3654190067u, 3585109483u, 2170692034u, 4104050396u, 1431760441u,
     871040163u, 3131221596u, 4039637966u, 3255680597u, 1537348827u,
    4274038615u, 2766931218u, 3080056590u, 2427576150u, 1698622741u,
     491269657u, 2957152254u, 4003327323u, 1665870563u, 2898998885u,
     350910601u, 3377912239u,   56558544u, 2757732126u, 3003019578u,
    3020476484u, 1103562767u,  266867533u, 3238470691u,  101050052u,
    2174141449u, 4261294044u, 3377977245u, 4283033233u, 1649319944u,
    2407542500u, 1186270608u,  506638155u,  853299114u,  528018288u,
    3370360190u, 3432726533u,   33304936u,  746516661u,  864441540u,
     877624554u,  549536499u, 2512486873u, 1718378202u, 1877264374u,
    3907125156u, 3480301523u, 1222420918u, 2962412787u, 1897386667u,
     565602854u,  870635873u, 1837265416u, 2093005006u, 2069832336u,
     421542850u,  546177829u, 3737295211u, 2022730805u,  114777545u,
    1045010491u, 1474827040u,    7636789u, 3926378049u,  825140914u,
    3894878768u, 2235348820u, 4209167372u, 1363271078u, 1633012431u,
    2604598105u, 1475584955u,  363136592u, 2939993958u, 3395026321u,
    2769982499u, 2579982422u, 3377853512u, 1926697291u, 1309179303u,
     198769522u,  525328917u, 2939632387u, 3839345362u,  857890368u,
    1404166316u, 1175685399u, 3359187637u, 2911320684u, 3331860351u,
     150684895u, 1830720677u, 3549325302u, 1721173678u, 1541682359u,
    3727128665u, 1378619663u, 3657645799u,  427125659u,   87651116u,
     816648775u, 1111028388u, 3408906806u, 1198529401u, 4082457652u,
    2373720194u, 1279364663u, 2697296422u, 4274091187u, 3991008751u,
    2750937690u,  745247050u, 3020601003u, 3207637609u, 1522623855u,
    3440826157u, 1459824707u,  275982735u, 1366156119u, 2084141301u,
    3371738706u, 3652235981u, 3414352861u, 3867568134u, 4143632352u,
    2508301197u, 2694712076u,  663648113u, 4084805516u, 2045731357u,
     103690742u, 3579296438u, 3853685199u, 4040332527u, 3433047383u,
    2160986205u, 3880533570u, 2124079194u,  898702193u, 1377522152u,
    2510928900u,  524137274u, 2676839533u, 1147766985u, 2659663351u,
    1441686856u, 2336342795u, 2323419808u, 2616909909u,  367789898u,
    2802090548u, 3912305190u, 3394874017u, 4182826382u,  378652856u,
    2456117771u, 3644581920u,  650421961u, 1356327939u, 1270283631u,
    1353114655u, 1186775090u, 2229315614u,   60977715u,  255049167u,
    1393113108u,   91557822u, 3460789587u, 4255756627u, 2680883563u,
    1961238627u, 2706826361u,   86694213u, 3568183186u, 1174931951u,
    3101787400u, 3245440880u, 1012545275u, 4023587262u,   25415056u,
    3884392715u, 2033651573u, 1517048548u, 2157890606u, 1607160396u,
    1733385865u, 4000967569u,  702762527u, 4219828471u, 2839214666u,
    3612303148u, 2417079479u,  561191037u, 2668684575u, 1049452531u,
    3056008028u,  752063538u, 1442500991u, 2201174758u, 1248774154u,
     165187750u, 2945670372u,  435357616u, 3927358478u,  535926151u,
    3753175365u,  256444691u, 2255485820u, 1023308722u, 4229846989u,
    2519054772u,  651526182u, 4180758060u, 2654793384u, 2610214273u,
     610288969u, 1979520346u, 1745042640u, 2256795625u,  954259986u,
    1077808451u, 2678875090u,  955102447u, 2059446553u, 3293602562u,
    1583006223u, 2748412790u, 4129522985u, 1799912684u,  461379416u,
    3072251629u, 2023808855u, 3368588935u, 1852160624u, 3234147626u,
    2398022056u, 3965955751u, 2934088597u, 2993217622u,  750328728u,
     783088312u, 3770678320u, 3156679282u,   36274327u, 1466406645u,
    4053852068u,  438490559u, 2718496037u, 3313180021u, 2382533773u,
    3930250216u, 3894526091u, 3389067170u, 2754596462u, 2355173790u,
    2384382760u, 2238960674u, 1652306376u, 4043138340u, 2268422975u,
     702886942u, 2158419984u,  313074687u, 3916694140u, 2872536179u,
    4110613033u, 3497889789u, 3345443240u, 3438724296u, 3831640476u,
    1721511461u, 3181187841u,  293747726u, 1016981259u,  319715874u,
    2604613639u, 3866375162u, 1129514664u, 4090305697u, 1415656234u,
    3904058353u, 3454231580u, 1137421991u, 2313708721u, 3189903818u,
    2359396326u, 4140811458u, 2619162542u, 4018716781u, 2943094968u,
    4275110940u, 3753225546u,  393641299u,  793819538u, 3807603495u,
    3584270096u,  583337815u, 3204343682u, 2704728429u, 1260285383u,
    2070005280u, 1290966975u, 3841613013u, 3748951459u, 1996539050u,
      15255144u, 3555533616u, 1896042895u,  457790456u, 2103229914u,
    3549835684u, 2608881213u, 3750997458u, 1284886852u, 3983637798u,
    2754133138u, 1375874601u, 3702999536u, 4047595327u, 1757722874u,
     205211433u, 1550020058u, 2625086805u,  888856283u,  260526089u,
    3603211830u, 3874949683u, 3705639611u, 1244107692u, 2576564054u,
    1798606541u, 1538798258u, 1914115295u, 3465780481u, 2191768384u,
    1053339258u,  482479463u, 1590615673u, 1678894824u, 2583029443u,
    3312998864u, 2348965967u, 3592411649u, 2586886059u, 1193775683u,
    3166643410u, 2848176518u, 4244785412u, 3263141460u, 2534433066u,
    3857841146u, 4030264873u, 2160049808u, 2568607774u, 3962849448u,
    1063016183u,  752325873u, 3916513901u, 3666512065u, 3742123864u,
     240316886u,  273053100u, 1974725783u,  103853041u,  498343646u,
    2849277012u, 1531820781u, 2800822870u, 2172374911u, 2608056220u,
    2938222996u, 2495640435u, 2050031019u, 1581664696u, 1192708798u,
    3958663429u, 3409883558u, 1261646904u, 2262137662u, 1495935118u,
    3549216229u,  819898291u,  616300818u,  920698111u,  531434903u,
    1750605108u, 2331202523u, 2604625024u,  311416415u, 3413350776u,
    4091626041u, 3339815970u, 2156981844u, 1053778854u, 3946541364u,
     757561673u, 2794628342u, 2560288402u, 3516100843u, 1078950707u,
    1096405570u, 2565723989u, 3166139486u,  665944531u, 3426830504u,
    1316229722u, 3470576224u,  174450923u, 1756691252u, 1809953431u,
    2120869441u,  744710690u,  638114562u, 3462360879u,  662650689u,
     654132881u, 2029278034u, 4053373589u,  659248560u, 1754023002u,
    3683623866u,  684016545u, 2635610107u, 3319934252u,  877308702u,
      32003886u, 3136239345u, 2204537667u,  617587244u, 3444132147u,
    3394465910u,  707665795u, 3673280986u, 2732829120u, 2865909493u,
    3553125825u, 2860898385u, 2982421098u, 1193861977u, 1034606365u,
    1752852792u, 1621071619u, 2528057870u, 2138762952u, 2308749354u,
     906867989u,  779669216u, 2232060698u,  480996617u, 2925606018u,
     303678891u, 3851015553u, 3348999586u, 1213516375u, 3489393664u,
    2606497132u, 4155605153u, 3740915058u, 3037706031u, 2239177712u,
    3123401220u, 1990275519u, 3162603957u, 1918939652u,  776035672u,
    2865857149u,  571764668u,  151622100u, 2353602509u, 2112275436u,
    3057460223u, 1545579966u,  257397390u,   19209971u, 2138790032u,
    3753848035u, 1085255822u, 4235734180u,  875019346u, 3217942945u,
    1091459686u, 3587756657u, 3077984076u, 1491592709u, 3017547658u,
    2252844554u, 1985555588u, 3040031536u,  558425569u, 1123411656u,
     173859531u, 3673271296u,  495041198u, 1342690724u, 2894423806u,
     673054854u, 3159268470u, 3113987190u, 2436187367u, 1936640302u,
    1360880324u, 1912925050u, 1245740864u, 1374924892u, 3948122288u,
    3665262872u, 1730168177u, 1418975463u, 1724598953u, 1518264520u,
     155679217u, 2777491364u, 2127704373u,  479136316u,  467963358u,
    2038497471u, 4009847343u, 3214679953u,  316320711u,   43436245u,
    2439770433u, 3061525191u,  325285125u, 3418463477u,  265361904u,
    3317034447u, 2046949609u, 2398727149u, 3035501454u, 3766818899u,
    1907069371u, 3915369678u,  825294741u, 3960827812u, 2822610696u,
     435348151u, 2960342732u, 2841517289u, 1245939424u,  501966471u,
    1523054284u, 2986922068u, 3643707400u, 1960129231u,  605842596u,
     498475817u, 2091802075u, 1546806085u, 4249712391u,  719048827u,
    1236161870u, 1455705076u,  611924837u, 1606154038u, 3804768796u,
    2147049065u, 3141135911u, 2326016873u, 1938285117u, 2106616699u,
    3649256942u, 2518864732u, 3041005008u,   25486255u,  317223081u,
     859651472u, 3423179818u, 3316420743u, 1720381191u, 2949551625u,
    4153784543u, 2375654557u, 4245912914u, 3055577422u,  426826876u,
    3371315320u,  393263103u, 1674632271u, 2001097492u, 3810913408u,
     926582509u, 2004092737u, 1225977080u,  704646682u,  507362042u,
     115002871u,  772062004u, 2509172666u,  671380383u,  741064994u,
    1087280005u, 2458813622u, 3555270161u,  432569830u, 1768785658u,
    2788242172u, 3626575210u, 3924321291u, 1056700312u,  807145567u,
    2457173701u, 4163083585u, 2389340792u, 2527897320u,  148652138u,
     809466003u, 1310067162u,  147554547u, 3006884242u, 1648641905u,
    2507398430u,  286276539u, 1285247198u, 1497575669u, 4272381767u,
    1630690228u,  528903131u, 3782308744u, 3328620223u, 2544636753u,
    3716824890u, 3359475073u, 1715425081u,  493809452u, 1482469337u,
    2880570645u, 4246120078u, 2462260788u, 4005994348u, 3376710207u,
    3055770626u, 1224220146u,  706700781u,  146623188u, 1905647200u,
    1835596148u,  114826369u, 1833749674u,  534781147u,  233967048u,
     942256881u, 3699192716u,  188293730u, 3910438208u, 2394758371u,
    3662527011u,   97504699u, 3543922236u, 4206828553u, 3734565571u,
    3586763714u,  403958048u, 2063667481u, 2730205743u,  589502476u,
    1149905623u, 4095869863u, 2805195184u, 4223446468u, 3102461252u,
     423688803u, 4256209713u, 1518355137u, 4269931685u, 4174808463u,
    2019550169u, 1704760048u, 1718939701u,  602013714u, 3655037789u,
    1997992275u,  782052616u, 2168800816u,  284956141u, 3975978923u,
     644864581u, 3042712626u, 2180684793u, 1466664828u, 1267605484u,
    2784735889u, 1428685493u, 2544323949u,  889906898u, 4235848255u,
    4186602195u,  855556210u, 2342896146u, 3307519234u, 2197566638u,
    2509561763u,   20519604u, 2319402891u, 3907092227u,  805926263u,
    1545081676u,  946901149u,  174874593u, 2904667651u, 1004586041u,
    1671610396u, 2507164708u,  565710128u, 2195671193u, 2148970716u,
      64150785u, 3111996478u, 3853037378u, 3929028523u,  992899482u,
     698318534u, 1024524470u, 4196904510u, 3557517929u, 4285406934u,
      94205271u, 3530304939u, 2305824750u, 1531731847u, 2100892683u,
    4141695457u,  717968711u, 1020961798u, 1435297145u, 1174399738u,
    3484051255u,  401988634u,   18353084u, 2476579762u, 3884197419u,
    2161379550u, 3488516503u, 4291859194u,  429223686u, 2634560425u,
    1960550128u, 3018314044u, 3956111413u, 3586019740u,  271458754u,
     995152322u, 2784808343u, 2699155930u,  718003490u,   88374071u,
    2116640876u, 2418838888u, 2473871392u, 3887260803u,  291756441u,
     317239670u, 1991643081u, 1067021559u,   52172441u, 3466077380u,
    2808782519u,  506095445u, 2721138411u, 3170096146u, 2636465745u,
    3084352426u, 1216338971u, 1227230645u, 3998968120u, 2009459829u,
    2474360224u,  345636082u,  601138538u, 1362885697u, 3578651252u,
     698241090u, 1118227414u,    5507337u, 2780083822u,  703266438u,
     864120870u, 1698678511u,  172897137u,  144366506u, 1820854951u,
    2113926171u, 3294417442u, 3001580140u, 3365898069u, 2414288823u,
    2191315816u, 2041923551u, 1374216245u, 1792102283u,  966439255u,
    3142541052u, 3926566349u, 4034829900u, 2276773096u,  381471573u,
    1895081823u, 1362996393u, 2592249580u, 2898726226u, 4223177326u,
    3400414171u, 2052800787u, 3853885905u, 1028196740u, 3183947606u,
    2486531127u, 3167268159u, 1866096562u, 2950293380u,  994523562u,
    3023614567u, 4104267478u, 1191097596u, 3529256093u, 3418504368u,
    3894797255u, 3908535736u, 3298561721u, 3288395583u,  912501104u,
     831862193u,  858008061u, 3583526686u, 3604044732u,   11642333u,
     532352558u, 2447342506u,   49917723u, 2465972387u,   49071225u,
     189297954u, 3406843807u, 2379895567u, 2252069007u, 3118935217u,
    2612642690u,  489772543u, 3046688150u, 1991370098u, 1491676633u,
    2171172062u, 2631485941u,  111539597u, 1754135798u,  104108364u,
    3801121441u,  961805875u, 3244343746u, 3927144143u, 1042956596u,
    2171259252u, 1546798356u, 2949756312u, 1677484392u, 3916024040u,
    2117087490u, 3806450987u, 3716708844u, 3052844593u, 1098132833u,
    1944120348u, 1211978277u, 1373013705u, 1417003306u, 1935792551u,
    2645561211u, 4148953952u,  530900685u, 4282117874u, 1246946090u,
    3856432168u,  239949635u,  140665127u, 3955560396u, 1458503553u,
     141173732u, 3283724848u, 2719866813u, 1750621676u,  550663579u,
     491600368u, 3263446369u, 1961062013u, 1243373458u, 3444793917u,
    3899300498u,  718538962u, 3064564239u,  101084001u, 4001046471u,
     690719870u, 2544332192u, 2973901205u, 3510440400u, 2221840969u,
    3581406537u, 2687583608u,   45358658u, 1597859661u,  314280821u,
    3494340276u, 3133266884u, 1787593645u,   87373007u, 3037573439u,
    3752761966u, 1788735812u, 2276942058u, 3166047868u, 1996038283u,
    3602485091u,  493959987u, 2734283831u, 1597766558u, 1319887499u,
    3957554749u,  967477137u, 1871108451u,  366543865u, 3417930960u,
    3465456271u,  683117185u, 2140844389u, 1633256418u, 3595239200u,
     272311865u, 3868727953u,  516898363u, 2749883233u, 3669048734u,
    2889507150u,  343253656u, 1307200448u, 2276582436u, 1455456255u,
    3095475925u, 3167968348u,  753145196u, 1720643028u, 1964199342u,
    3245346896u, 2501510517u, 2401288980u, 3190253603u, 3392954261u,
     927482091u, 2739586668u,  656503075u, 3631723682u, 2774039073u,
    3581048448u, 2109905006u, 2654627331u,  625449654u, 3921753764u,
     533200192u, 1708723687u, 3105862488u, 1938982508u,  284773522u,
    3014100134u, 2332799199u, 3899421698u, 4054778144u, 1855118412u,
    2423445164u, 2085429129u, 2525269691u, 1050404537u, 2665308718u,
    2195447044u, 1546419073u,    6271311u,  848651525u, 2114666412u,
    2361256342u, 1968111351u, 2378425902u, 2399819062u, 2046693061u,
    2184541122u,  606566810u, 1184406086u, 3849119084u, 1782109246u,
    1711162988u, 3725213412u, 1978982002u, 2084076307u, 4226808472u,
    1381220175u, 2756022796u, 1155923374u, 1310996083u, 3892088705u,
    2900168226u, 2172331364u, 1976800812u, 3446717919u, 3018115416u,
     772796339u, 3119675141u, 3399966733u, 2483366635u, 2251157986u,
    3721643942u,   92354950u, 2276558847u, 3199161030u,  391156337u,
     516105765u, 3031568469u, 3056187358u,  327152205u, 2268820210u,
     154728704u, 2498616329u, 2687795551u, 1661550221u, 3058059426u,
    2011392238u, 3213116060u, 4232673760u,  188451691u, 2316494518u,
     139654414u, 2820632408u,  741805800u, 3398953290u, 3029114036u,
    4228239470u, 1294389995u,  220293836u,  832710216u, 3520956438u,
    3326239211u, 2002353592u, 2910456568u, 1116726602u, 3947894185u,
    2269194026u,  331201566u,   23448299u, 2501636454u, 1481063438u,
     531225803u, 3374157189u, 1250339898u, 2807211779u, 3509443222u,
    3149299112u, 2512315800u, 2156034521u, 3927375017u, 3009858040u,
    3815089086u, 2493949982u, 3668001592u, 1185949870u, 2768980234u,
    3004703555u, 1411869256u, 2625868727u, 3108166073u, 3689645521u,
    4191339889u, 1933496174u, 1218198213u, 3716194408u, 1148391246u,
    1345939134u, 3517135224u, 3320201329u, 4292973312u, 3428972922u,
    1172742736u,  275920387u,  617064233u, 3754308093u,  842677508u,
     529120787u, 1121641339u, 3300737790u, 3072286611u,  763885092u,
     237936516u,  214735112u, 1071670392u, 2640290649u, 2253339066u,
     406563643u,  857883160u, 1943298024u,  482572274u, 1387459037u,
    3227802952u, 3719718158u,  254239224u, 2056147900u, 1907664448u,
    3028647233u, 1385596859u, 2691640069u, 4156402531u, 2727923167u,
    2529722889u, 3095622616u, 1958102896u,  576816725u, 1327262146u,
     614269765u, 1721856728u, 1312650621u, 2437977684u, 1733921636u,
    2123749922u, 3790190001u, 3934886640u, 2878714597u, 2564557568u,
     157082304u, 2081155532u, 1874993431u,   29873796u, 1575628456u,
    4088191944u, 2658510623u, 1984791300u, 3812698918u, 3787281972u,
    4231096806u, 3785648472u, 2977746737u,  671867256u,  898437006u,
    1316824526u, 2640443682u, 1404000060u, 3276358491u, 4161289148u,
    1102117255u, 1256660265u,  209840788u,  385024522u, 2368673317u,
     323107512u, 3455934026u, 3731694261u, 3391583476u, 2939001717u,
    1103408741u, 1083361420u, 1698019267u, 1565815683u, 3463127127u,
    3731607982u,  697017152u,  734146234u, 3016440987u, 2640822923u,
     468448749u,  400190664u, 1063137237u, 1360374355u, 4071057687u,
    3077992194u, 1418755066u, 2114340252u,  507520129u, 2219575806u,
    2032764621u, 2022031889u, 4206268338u, 3431678471u, 2027400693u,
    2669084807u,  831934007u, 2741455826u, 2363266155u,  246856212u,
     632436514u, 3515740889u, 2195525760u,  971767468u, 1276384569u,
    3850605480u,  249929275u, 4103572387u,  173516974u, 1665191261u,
    3656906633u,  323924265u, 2631672499u, 1675859583u, 3734620872u,
    1388796197u, 4080779261u, 2337389174u, 2655227505u, 2543838574u,
    3971410265u,  420679752u,  496026352u,  186764349u,  165231151u,
    1627667691u, 2166211449u, 1762978544u, 1450698279u,  244833631u,
    3701624698u, 3546129192u,  432955709u, 2578973523u, 1268347370u,
    3585006787u, 3065734222u, 3840890096u, 2730792797u, 1190210715u,
    1229058459u, 2004508211u, 2236271394u, 1163898177u,  317061964u,
    4104512475u, 3981785820u, 2724518087u, 2447324937u,  612066133u,
    3833016990u,  581709676u,  709654776u, 2295002741u, 1137254807u,
    3385935788u, 1271908877u, 1575381586u, 3541074184u, 2662027818u,
     578812846u,  695633467u, 3826065625u, 2352553817u, 1189926887u,
    3949219588u, 1149364385u, 1140956216u, 2758597267u, 2208280441u,
    2004286835u,   23811599u,  101605991u, 1718702543u, 2565308531u,
    3504199076u, 1093913647u, 2943472056u,  208957281u,   93183733u,
      26200246u, 2515020035u, 3147530638u, 1167877885u, 4173286473u,
    3769999835u, 1316803433u, 2676177653u, 2249893478u, 2728386872u,
    1289080741u,  108414488u,  911939596u, 3631792077u, 1201915048u,
     443256488u,  695071951u, 2382437614u, 2026588982u, 2632432926u,
    3752320434u, 2522821802u,  645589903u, 2852069592u, 1507054019u,
    3446656352u,  352137468u, 3660766493u,  659827898u, 2694662642u,
    2414681487u,  981423112u, 2969509231u, 1181913590u, 3283845787u,
    1579289584u, 1736014821u, 1868176940u,  944873323u, 1817775084u,
    2530710862u, 1627730672u,   66245778u,  675589177u,  926873064u,
    1555989601u, 3241218062u, 2208111558u, 2091107069u, 2186880097u,
    1922662991u, 3262102331u,  407680084u, 3225806537u, 1728234429u,
    2815516280u, 1467728810u, 4113584515u, 2523822574u, 3907401252u,
    1890262741u, 2857922946u,    9312338u, 1743264483u, 1703482351u,
    1125583605u, 3170904314u,  738854734u, 1759558300u, 3184633114u,
    1178715144u, 1960548124u, 1037689637u, 2750727957u, 3611858166u,
    2361354361u,  467381126u, 2712884168u, 3111383860u, 3607434155u,
    2140986302u, 1659435938u, 2870614947u,  483402068u, 3327353724u,
     173441805u, 2892921505u,  322459867u,  342084856u,  476285132u,
    2067116357u, 2987638716u, 3139221121u, 3648371306u, 2249325349u,
     616697281u, 3744830951u, 1842700074u, 2971192596u, 3726408523u,
     109869626u, 1487813247u,  885160389u, 1639902238u, 2438016503u,
    2809256484u,  467766414u, 2269768842u, 3533241669u, 1626201598u,
    3396738581u, 3323794334u, 1684642258u,  630214583u,  683085617u,
    1860535308u, 1692841768u,  213970453u, 1620501115u, 2950013140u,
    2600979684u, 3101788642u, 3940886529u, 1051539558u, 3444502811u,
     686778540u, 2040757101u,  453012501u, 2726351009u, 2450885997u,
    3954218997u, 2161221709u, 4273602338u,  315911737u, 3837424460u,
    3983366596u, 1961106069u, 3092378093u, 3794692952u, 3936554087u,
    3931909059u,  403814402u,  494561694u,  735241236u, 1852073032u,
    1338882628u,  253049925u,  831176075u, 2962932411u, 2624182132u,
     276217644u, 2654594797u, 3505958190u, 2643143479u, 2909381563u,
    2812077621u, 2561795171u, 2649734514u, 1600038684u,  572123377u,
    2903239907u, 3676987477u, 1946232532u, 4192788977u, 3352250323u,
    2072925788u, 3243132465u, 2710328260u,  559282756u, 2496495841u,
    1663691009u,  289654448u, 3463704651u,  892590470u, 1840421798u,
    3271090533u, 4143706049u,  617178688u,  134482073u, 2269042691u,
    3230232400u, 1073622572u, 1292832927u, 1514583707u,  343422799u,
    2568797335u, 1703121731u, 4246032950u, 1125492680u,  840571992u,
    2904558028u,  373108020u, 4002658231u, 3705499974u, 3080886235u,
     381031087u,  516747576u, 1882498794u, 2655103969u, 1722338904u,
    3506481279u,  954136253u, 2194640986u,  458904938u, 2230909876u,
    1232295042u, 4026050644u, 4268594314u,  386790887u, 4165330488u,
    2512717163u, 2939124594u, 2996196263u,  751292327u, 4220296919u,
    1806647125u, 3424044432u,  529412756u, 2785560848u, 1277215461u,
    1255562273u, 3182925185u, 2338361557u, 1825211939u, 3677840444u,
    1711411618u, 1758593657u, 3511837694u, 1349462441u, 3428028389u,
     830423639u,  916445791u, 1046053695u, 1356825518u, 2206311325u,
    4024885318u,  761804059u, 1750908698u,  633217941u, 1238957827u,
    4111074188u, 2364254471u, 4075930521u, 3987296879u, 3614538834u,
    1681622248u,  233233044u, 1350971022u,  703752965u,  742511090u,
    1319273373u, 1551556057u,  801526694u, 2261637738u, 3429584111u,
    2522240856u, 4033776321u,  993802642u,  276019073u, 1802442104u,
    1624529825u, 3688548619u, 1428574037u, 2759605887u,  714112429u,
    2464378249u,  790901819u, 1071757684u, 2328808137u,  745645834u,
     549566994u,  812008863u, 1682615503u, 1156655121u,  601964903u,
    2388185358u, 2263159343u, 2449211150u, 1437661351u,   12615427u,
     215564646u, 2484119735u, 2932155371u, 1762139369u,  158159499u,
    2365521282u, 2277660798u, 3067589594u, 1443309319u, 3875571875u,
    3148481662u, 4251148624u,  899549959u, 2383987797u, 4054743020u,
    1617718571u,  764855974u, 3623170507u, 1294195985u, 2092418947u,
    1392907274u,  259338315u, 2169056952u,  486370816u, 2608182505u,
      58281361u, 2489916780u, 2571322701u, 3789374714u,  451393610u,
    1906658293u, 1412587058u, 4038584782u, 3111791370u,  614696571u,
    3167192919u, 3717660107u, 3195921972u, 3815660283u, 3041128023u,
     570765305u, 3981085879u, 1107446894u,   51726088u,  293239046u,
    4206823928u, 2266071917u, 1624419600u, 3390262152u,  177263260u,
    2064461558u, 1929086034u, 1656019088u,  501074449u, 1715323410u,
    3733759909u, 2474982900u, 2025499441u,  969019452u,  659526089u,
     840640563u, 2500391789u, 2464587729u, 3777665909u, 3610207335u,
    4206950686u,  663950423u, 3911031610u,  374291529u, 3602165615u,
    3828747911u, 1422398845u, 2633015130u,  911010235u, 1250039282u,
    3668786465u, 2146176295u, 2998145602u, 3953806681u,  861918991u,
    3533426566u, 1195908145u, 1897435392u, 3160397475u, 4038157920u,
    3159042522u, 1607720526u, 2381657876u, 3862186850u, 3469342849u,
    3639212634u,  112769417u,  452688082u, 1414408784u, 1229308228u,
     507438193u, 1310342177u, 3867043376u, 3493923869u, 4076344759u,
    1432407149u, 3844851205u,  292787671u,  889906511u,  858447165u,
    4280160501u, 1754833546u, 1022797317u,  141082305u, 1717313637u,
     341442863u, 2982165294u, 2660069911u, 2284313116u, 3729297709u,
    3404076394u, 3170976459u,  594201128u, 2041497718u, 1243196847u,
    1266663238u, 2859272421u, 3185066266u, 3090105225u,  126778336u,
    2792308627u, 2668313630u, 1239558284u, 3271595203u, 3721632713u,
     408692953u,  136209149u, 1308802615u, 2102270171u, 3155640269u,
     326440485u,  295730848u,  523452312u, 3849023707u,    3647301u,
     591283519u, 3240559410u, 3618341580u, 1257535485u,  749043246u,
     214257867u, 2969963854u, 2265255083u, 2433422659u, 3703613001u,
    1868981396u,  219206218u, 1921827284u,  827842542u, 1269673531u,
    1710834839u, 1027401811u, 3163026058u, 1902411060u, 3815930641u,
     621420248u, 2054777317u, 4124947909u, 2353234036u, 1977996769u,
    2808784096u, 3225046473u, 2931747545u, 3142843391u, 1659837986u,
    1888420283u, 4259740486u, 2350930487u, 3413152075u,   56968219u,
     192969628u, 1423057188u, 1444249660u,  171197140u,  937248230u,
    4099400349u, 2399265778u, 1578088554u,  775063037u, 3858403452u,
    4225434954u,  478205274u, 1845362180u,  308036862u, 2216561886u,
    2390053622u, 1312984120u,  465471307u, 3916802888u, 1751063625u,
    3071743500u, 3294521276u, 4183444410u, 3328792670u, 4051235372u,
     938291851u, 3776732923u,  519625569u, 2466919130u,  979838570u,
    2725879728u, 1317420913u, 1463872356u,  637221019u, 3745811724u,
    1494600622u,  893750819u,  930858754u,  650342654u, 2192050103u,
    3365807907u,  873848167u, 2720924319u, 1145370623u, 2760666947u,
    2161896752u, 1105360170u, 2076071521u, 2063127636u, 3903444955u,
    4210510508u, 1867287227u, 3901733700u, 1228642505u, 1554715107u,
    1256194637u, 3463194748u, 2108350785u, 3137801541u, 1377619644u,
    2043599410u, 3670507577u, 2409694355u,  578584004u, 1915114417u,
    2964200468u, 3084637701u,  487846941u, 3464913449u,  851931544u,
    4091230055u, 3804622813u, 4062654036u, 1956958041u, 3982899036u,
    3060878573u, 1850342510u, 3229380710u, 2199978100u, 3449841444u,
    3404506672u, 4172579909u, 2858341611u, 4201756291u,  866708640u,
    2147611665u, 2927066921u,  981820178u, 4145753222u, 2926114981u,
    3142973742u, 3211993392u,     665956u,  186208327u, 2578776459u,
    1544585027u, 4147670018u, 3264346428u, 3529968586u, 2309075249u,
    3880526621u, 2125072657u,  481117536u, 2544413573u, 2202704127u,
    1672537106u, 1318470792u, 3554362612u, 3127591861u, 3015316471u,
    2945509163u,  291484478u, 2591981327u, 3245148648u,  739576946u,
     515232136u, 2261837125u, 1917651136u,  579070195u, 3597260689u,
      49188367u,  267006895u, 4276877494u, 3617401212u, 2853129749u,
     935399421u, 1080878326u, 3188786708u, 3498791570u, 2384965785u,
    1857094951u, 3407819412u,  704533477u, 4082950861u, 2567290570u,
     395265201u, 2047624633u, 2518905836u, 3372367611u,  801791416u,
    1901227854u,   38637635u, 3474202199u, 2474398228u, 1480879307u,
    2850068007u,  692791272u, 1196752290u, 1921623773u,  740690709u,
    3711563566u, 3014897166u, 1153198973u, 2587583270u, 3871261165u,
    1304143030u, 1562173300u, 2399579836u, 3387085571u, 3066436323u,
     273753460u,  548762751u, 4066258498u,  509964679u, 3892230842u,
    2594454158u, 2641210074u, 4000290307u,  197544729u, 1226784640u,
    2052493941u, 2015636260u,  619774998u,  610310685u, 3315794687u,
    2524554198u,  109352219u, 3966261588u, 2482511907u, 3321871424u,
    2144425402u, 3701574588u, 2168304673u,  382053842u, 4264336703u,
    1620184274u, 2591819932u, 4150402746u,  765308994u, 2759980202u,
    4277805943u, 1345011665u,   27080389u,  350826709u, 2183825604u,
    4075076920u, 3445501223u, 4190013503u,  587180938u,  214271696u,
    2154236153u, 1586367270u,  815350360u, 1444414461u, 3464262453u,
    3976631943u, 2834310035u,  447344574u, 3456943467u, 1857849941u,
    3288069997u, 3622828139u, 3766385238u, 1019699309u, 3574414672u,
     664756051u, 1488760916u, 3602182757u,  501971136u,  361544844u,
     638366795u, 2663513669u, 2577492878u,  288332466u, 1438600995u,
    1325679288u, 3124931681u,  317950919u, 2003481973u, 1680270394u,
    3336913304u, 4046786960u, 3928470606u,  379294149u,  258217508u,
     137055764u, 1536935606u, 2068904415u,  245653279u, 3279034418u,
    2000767513u, 1483858296u,  661632107u, 2388498781u, 2717721443u,
    3490673092u,  408205055u, 3671951051u,  422302660u, 3750077128u,
    3487755911u, 2475111658u,  225226079u, 3266015962u, 4163085962u,
     160505654u,  826502426u, 3108568799u,  235837591u, 1843748945u,
    3398011821u,  488014602u, 1703998678u, 2501340486u, 2457941993u,
    1583675704u, 3998234784u, 1823676750u, 1727161627u, 3026833773u,
     906959134u, 2137574027u, 3944299473u, 3781089529u,  724146943u,
     358776094u, 3525324801u,  185536569u, 1029340467u, 4177714978u,
    1881106148u, 2149519719u, 3090610550u, 1595510459u, 4026033108u,
    1758720811u, 3443479698u,  579449978u,  166684833u, 1954913591u,
    2436559945u, 3713643208u, 2787556827u,   80124672u,  668793893u,
     984001090u, 4172095298u, 1237562645u, 4246985448u, 2944124287u,
    4066835174u, 1203297508u, 3814830417u, 1041598911u, 2553744546u,
    1696041541u, 2537753781u, 3964937529u, 1275077003u,  396554334u,
    1508985930u,  257718692u, 3339554426u, 2816402520u,  120951742u,
     475928291u, 3224192115u, 2290598180u, 3010053799u,  232875814u,
     340483867u,  518492981u, 1202103710u, 2360369545u, 2906122107u,
    4156373681u,  475597219u, 1589253586u,  146259718u, 1926066295u,
     479682976u, 1340900563u,  827889393u, 1244772727u, 1312527732u,
    4198626021u, 3996441052u,   10644110u, 3247648552u, 1281332215u,
    3860750678u, 3285923885u,  186872129u, 3865515020u, 3302355353u,
    2477862790u, 3310744082u, 3841112686u,  677846076u, 2053589237u,
    1932534256u,  559147278u, 1877030045u,  385124408u,  254461835u,
     508013400u, 4278960989u,  316600986u, 3139554192u,  118560138u,
    1206070571u,  946801128u, 1202200929u, 3533120670u, 2072176200u,
    3754732210u, 2202753449u, 2497549341u, 1824188449u, 4096170263u,
    1778678071u, 2755925781u, 1162425729u, 3525283794u, 2549672156u,
     186047547u,  949616424u,  514250452u,  428000582u, 1402456747u,
    3275087661u, 1662527311u, 1062266134u, 2896808207u,  546372435u,
     426202384u, 2470040092u, 3679462914u, 2850980138u, 4246129126u,
      15470179u,  414350056u, 3096151869u,  389632407u, 2047499061u,
     378474270u, 4081137159u,  536430886u, 1728154601u,  698697206u,
    1062097602u,  836724005u, 1142685433u, 3332408589u, 3512314929u,
    2582057314u,   14591221u, 3331171678u, 1926729414u, 1869132451u,
    2013918714u,  871594890u, 3319674255u, 1404734878u, 2348955092u,
    2795656019u, 1375503625u, 1259278002u,  257464350u,  813387295u,
     895153179u,  844238198u, 1634630496u, 3998472331u, 3344820330u,
     602607720u, 3622762973u, 1362293693u, 3720441663u,  769877944u,
    3615743708u, 2648039718u,  970534205u, 2056260250u, 2135791038u,
     451217943u, 1814422094u, 2393651123u, 1701892116u,  909762509u,
    1408803141u, 4126742002u, 1074833343u, 2157239058u, 3166377133u,
    4238930216u,  563692261u,  934622773u, 1780917021u, 3698369962u,
    2567120916u, 4099632335u,  278317364u,  699067013u, 1433276974u,
    3412965834u,  776182569u, 2945101563u, 1901527490u, 3590591554u,
    1104453414u, 1815882203u, 3901802352u, 2083417226u, 3151899284u,
     244057543u, 3209024595u,  147951658u,  756739207u, 1235768209u,
    3156017009u, 3193645212u, 1880049815u, 1295819147u, 1168515246u,
     974065603u, 3058698171u,    5709523u, 1911494647u, 3913099549u,
    3609249161u, 3867419584u, 1950266164u, 1036231561u, 2487793992u,
    2691309339u, 2942155942u, 2965968254u, 1746424309u,  253966721u,
    4244463819u, 2067463969u, 1950849308u, 1246571141u, 4097566328u,
     346406741u, 2506944995u, 2759023005u, 4117530649u, 2724202928u,
    2058774036u,  162803051u, 4227611518u, 3088016137u, 1658512262u,
    1416465784u, 2137055388u,  878100347u, 2277478293u,  525092662u,
    1741194555u, 1309123261u,  460520284u,  119434317u, 2016523652u,
    1640172061u, 3804988800u,  540190186u,  790962267u, 1460908145u,
    3688753525u, 3461703962u, 3039026826u,  578931852u, 1006670859u,
    3481601471u, 1918534958u, 1859686764u, 4023948837u, 3920621011u,
    2540003721u,   67137340u, 2043405341u, 3268848308u, 1306808385u,
    3605706053u, 1623313713u,  660869119u, 2853351111u, 3475175842u,
    2821734805u, 3814658188u, 3654921032u, 2472577430u,  754344802u,
    4088246401u,   88411392u,  700117482u,  703548004u, 2245532518u,
    2639673532u, 3977880118u,   50148058u,  931630340u, 4041558803u,
    3949109103u, 2965310022u, 1968230113u, 1448979683u, 2858564441u,
    1523429339u, 1452231187u, 2696376206u, 3594274238u, 1221549017u,
    2397200653u, 1488063947u, 2905130063u,  199399599u, 4073133774u,
    4237311111u, 3055565669u, 3367773316u, 3162354197u,  297828300u,
    4122926713u, 2903038630u, 2506015605u, 2493069266u,  396227382u,
    3064295038u,  389390920u, 1684789502u, 2022004674u, 1546447938u,
    2342558675u, 3323380043u,  593016737u, 3277745628u, 2071469665u,
    3550721728u, 2172088092u, 1279295579u, 4216165077u, 1510998944u,
    4075672776u, 2930025022u, 2136492188u,  182691603u, 4038078968u,
    1396096227u, 3273166256u, 2094934945u, 4099357359u, 1007544560u,
    3699672923u, 2300884465u, 2980210279u, 4244552370u,  589833589u,
     714003734u, 4002387247u, 3389813967u,  845344855u, 3827405748u,
    1095009851u, 1096246435u,  195059445u,  390829018u,   45983343u,
    2942709471u, 2338891311u, 1314753483u, 1040822690u, 3615731833u,
    2047806006u,  203722163u,  439422620u, 2262897255u, 2481399711u,
    2730149622u,  268361952u,  351807012u, 1796447121u, 3551647148u,
    3863815581u, 3930491804u, 3040825682u, 3498148643u, 3103447131u,
     292250033u,  226867327u, 3034518570u, 3275929931u, 3242711804u,
    3226789931u, 2600170516u, 3264262736u,  497730864u, 3847393656u,
    2138081132u,  156554468u, 2050395814u, 3341597363u, 3771202984u,
    3623479970u, 3811066097u, 4180581721u, 2728037769u, 2759868955u,
     121442518u, 3472315639u,  205237287u, 2850789567u, 2312554204u,
    1182211478u,   38967328u, 3702438304u,  375884310u, 3165268977u,
     983625816u, 2735905787u, 2508035244u, 3513180306u,   10812940u,
    2299525101u, 1370593040u, 2901849677u, 1637452236u, 1505988434u,
    1234543967u,  197861388u, 1930286607u, 1561122202u, 1215392833u,
    3981188336u, 3849737971u,  868629879u, 2183787208u, 3332599237u,
     966010177u, 1084918212u,   82969797u, 3808821963u, 1864232486u,
    3366209990u,  751714288u, 2695039573u, 1097849769u, 3022976865u,
     587638393u, 2744414517u,   63322775u,  770817695u, 2209918549u,
    1635742189u, 2095921391u,  495753095u, 2352947823u,  882910281u,
    3059789361u, 2202887209u, 2519930578u, 1983703178u,  525620646u,
    3007446873u, 3466043628u,  969502396u, 2222572818u, 3631038137u,
    3440085912u, 3544306054u, 2279011116u, 1361979741u,  247624876u,
    1609426453u,  633820846u,  457170537u, 3189982065u,  313104052u,
    1671772203u, 3987982914u, 3878607460u,  442784563u,  239669768u,
    1186013783u, 1469875483u, 2717949819u,  720088221u, 3130619991u,
     627890744u, 2164497000u, 2241323725u, 1539052750u, 4116364762u,
    3447090944u, 2435636794u, 1034457706u, 2225396704u, 2039700441u,
    2193560651u, 2759784453u, 2838663578u, 3925342473u, 4229223551u,
    3059096898u, 3615459818u, 1983004688u,  907253649u, 1326210552u,
    3579190630u, 3272911913u, 4131935105u, 1327722125u, 2908147995u,
    4092513009u,  746274712u,  736869831u, 1497858220u,  487961967u,
    2386169970u, 1439014353u, 2738069928u, 1944184985u, 3492078389u,
    2809697569u, 3555856753u,   74229530u, 1188033126u, 1042117947u,
    1505471861u, 1978689067u, 4284088321u, 1879582610u,  197373605u,
    1581803397u, 2542952419u, 2458103082u, 2609274498u, 1208734497u,
    3053599284u, 3356619347u, 2786163035u,  294958267u,   62146935u,
    2950201268u,  382600974u, 2796353027u,  480450472u, 1731575026u,
    4086256647u,  797880888u, 2653010568u, 2663080685u, 3860407534u,
    2658068184u,  807060335u,  674881738u,   51791346u, 2375548938u,
    2339108673u, 2765711021u, 2074225046u, 1909060248u,   20753244u,
    2726236940u, 2902081023u, 2864855158u, 2811409260u,  845253867u,
    3292451361u, 3033695434u, 3775963086u, 3602564352u, 4196643721u,
    3060262852u, 1753216383u, 2691205345u,   21535303u, 3469036080u,
    2125167827u, 3818146091u, 2837019400u, 2727529820u, 3494652317u,
    1112114299u, 2598168998u, 1146515049u,  108198915u, 3736718166u,
    2342983819u, 1756214915u,   39732867u, 1665876672u, 2145382992u,
     821052743u, 2839251707u,  649422276u, 2893622878u, 3782158454u,
    1964100944u,  553504817u,  921832272u, 2790668159u, 2937271603u,
     296629342u, 3972341743u, 4122628545u,  564370865u,  595711954u,
    1004248294u, 1452078904u, 4220574292u, 1346997234u, 1135155980u,
    2436887773u, 3222929103u, 2962393409u, 2323344035u, 3165484739u,
    1084131787u, 2525794560u, 1899607021u,  695377600u, 1997857469u,
      88053015u, 3734708914u, 2495304031u, 1581633088u, 2043722547u,
    4094560820u, 4226819750u, 3423672780u, 3994550009u, 3250795980u,
    2099028017u,  985784650u,  535968328u, 3219077037u, 2978028186u,
     292695848u, 3814517741u, 3820167765u,  200283462u, 2302587436u,
    4179722693u, 2429319487u, 2443111044u, 3933774850u, 3981281444u,
     847952093u,  411105399u,  125762624u,  299104240u,  191979292u,
    4260457698u, 1517829698u, 3157507235u, 2949795084u, 4045869099u,
     442379810u,  670507780u,  342615858u,   60683203u, 2084538822u,
     417237724u, 2900476740u,  490611202u, 2335306135u, 3861053900u,
     894868909u, 2241567518u,  109806941u, 1561361784u, 1267909589u,
    3504175937u, 2873638693u, 2322187772u,  918019581u,   90375045u,
    1322819651u, 4275087498u, 4210332957u, 3544888221u, 1627085930u,
     740314301u,  312214225u, 2148631325u, 3839821879u, 1647939052u,
    4048129244u, 4267208914u, 1216066417u, 3131565549u,  875267714u,
     515920142u,  402925233u, 2985339508u, 1088037711u, 2396879732u,
    2985692501u,  594266515u, 1245163848u, 3795178832u, 4101911396u,
     633610523u, 2036387890u, 1643319818u, 2737035221u, 4186394095u,
     299255052u, 2124154322u, 2903433416u, 2427607473u, 3406501268u,
    1153584787u, 3808804282u, 3574542198u, 3691414869u, 1247035742u,
    1840699692u, 1894792930u, 1111698354u, 4163650221u,  878895484u,
    4275109574u, 3605165959u, 2769656456u, 1792478603u,  653761709u,
    2922494638u, 3535305080u, 1050649815u, 1969236932u, 3145103665u,
    3434066363u, 2651068462u, 2685752418u,  710376912u, 1840537674u,
    3316779381u, 1484595551u,   51421505u, 2391514678u,  667590861u,
      17876313u, 3534564971u, 3837535426u, 1602866621u, 1174807010u,
    1015036918u, 3927229866u,  803183846u, 3496648295u, 4082962459u,
     918191827u,  183989530u,   17394283u, 2479064643u, 1243428848u,
    1373442572u,  353721777u, 1830492352u,  183135121u, 1501139126u,
    4013748963u, 3859067783u, 2918339539u, 3932596121u, 3504272451u,
    4175022285u, 1267953507u, 1659009980u, 1433962594u, 1519724836u,
    1659795277u, 3631005750u, 4207376111u, 1604931964u, 3717646468u,
     569940483u, 3230062768u, 2708673706u,  773344531u, 2911040214u,
    1867341976u,  863824450u, 3947365482u, 1273604501u, 1420223013u,
    2630908838u,  337462969u, 2093655521u,  678151284u, 3709558257u,
    2045368751u, 2930065301u, 3599726355u,  474927981u, 2317150878u,
    3736594619u, 2753555624u,  195271580u,   94274512u, 1709600363u,
    1794400717u,  885551916u, 2795594734u, 3607248528u, 1835059061u,
    2747843334u, 2328234907u, 1001035435u, 1693652345u,  235805936u,
    2638138829u,  547153028u, 3599697801u,  991695015u, 2877234179u,
    3383722389u, 3059481083u, 2627013253u, 3567440638u,  498287328u,
    3600036397u, 2959299970u, 2755364832u,  199929461u, 2562732425u,
    3937982401u,  861395241u, 2412532711u, 3435590095u, 2920201743u,
    3661847978u, 3022949305u, 3219949338u, 2562973337u, 3773797507u,
    2145098192u,  935077289u, 3667892744u,  124435112u, 2733153171u,
    2336633071u, 3049114028u,  296015014u, 2751679747u, 2396349832u,
    1496705403u, 3603954500u,  518868682u, 2578755152u,  736840699u,
    1805957349u,  666330774u,  608986249u, 2472363853u, 3800278416u,
      40896582u, 1680781511u, 2082409749u, 2249181642u, 2210280556u,
     357432911u, 2329972169u, 2886165767u, 2427904608u,  956912295u,
     971928712u, 3095355668u, 2911246641u,  482262902u,   60312911u,
    1312365275u, 2013765306u, 1783734131u, 2522610297u, 3690325440u,
    2709933595u, 1909940033u, 1442425499u, 1704357789u,  899484502u,
    2742977966u, 1497525367u, 1583123174u, 1318029612u, 2564838921u,
    3763856450u, 2514174710u,  198316421u,  265990530u, 1768395667u,
    2314710286u, 1683671620u,  221036278u,  571751506u, 2779207683u,
    1555945911u,  423155030u, 2047935335u, 1434018760u,  787022731u,
    3056004199u, 2284689631u, 4137760392u, 2701080567u, 1756642125u,
    3912131294u, 1201533467u, 3956594108u, 3526202936u,  519557376u,
    3159661834u, 3756697023u, 1583510448u, 1886607524u,  709938394u,
    2280781434u, 1612256833u,   53104508u, 2131060933u,  281397192u,
    1455261348u,  244810324u, 2671976612u, 2156407609u, 3899123681u,
    2484549899u, 4017599516u, 3837959347u, 2804179735u, 3994219050u,
    2424320044u, 3037372381u, 1925993718u,  332392405u, 1177246587u,
    4177876254u, 2845483154u, 1390491309u, 2938496931u, 1463164366u,
     707836749u, 2768827532u,  568741807u,  869407265u, 1280965775u,
    1172620039u,  478972532u, 2987000536u, 3805122215u, 1468413102u,
     543917782u, 3394277116u, 4044202117u, 1025405644u, 1707224750u,
    1864686183u, 2240605571u, 1290357116u, 4101884836u, 1991992160u,
    1996968929u, 3463552824u, 1219717543u,  502934926u, 3633464291u,
    1725958720u,  870640282u,   41924200u, 2386735502u, 3737713709u,
    2920533520u,  416930056u, 3319442073u, 3325200926u,  600730999u,
    2558036132u, 3509898830u,  601814492u, 3250106394u,  768972570u,
    1825868704u,  100617135u, 3218264529u, 1463864280u, 2589827818u,
    2671592874u, 2112587743u, 1139666942u, 1054938100u, 3705456107u,
    3529994423u, 2120736180u,  547125328u,  658109267u, 2980455600u,
     636600577u, 2182547042u, 1783330846u, 2735761548u,  299718758u,
    2517033811u, 3090526543u, 4228910553u, 1659076526u, 1860771466u,
    2936600089u, 3509421045u, 2979075421u, 3031364810u, 3195690080u,
    3566117579u, 1405740019u, 2816510332u, 3007319793u,  643248787u,
    4020853943u,  171580820u,  300129979u, 3969161736u, 4289646346u,
    3745142316u, 3090885346u,  584557670u,  634680948u, 3799101749u,
    2430972807u, 2748166655u,   15868433u,  735399278u, 2677365711u,
    3115162351u, 2206458278u, 1126454368u, 3266341386u, 1132674226u,
    2751051383u,  553029961u, 2593118860u, 1053466729u, 3597461159u,
    3933828494u,  663458002u, 2447294939u, 2927798739u,  492877382u,
    4236233329u, 2763528638u,  195002750u,  986046518u,  639830937u,
    1030191024u, 3193064705u, 1947250508u,  370040359u, 3154891784u,
    1054651402u,  929718775u, 3784950826u, 4235202677u, 3848447182u,
    1300324412u, 1614380154u,  793587525u, 1275759162u, 1938255782u,
    3962698057u, 3322334872u, 4097609677u, 2040562167u, 3963663159u,
     824929530u, 2196910585u, 3023064302u, 2785667685u,   27701234u,
    3002859705u, 3296503982u,  317114949u, 1695591138u, 2139548806u,
     965321175u, 3726861363u, 3331730566u, 1879689475u, 3480440163u,
    1300921036u, 1949052871u, 3348542305u, 2126207026u, 2571967031u,
    1969124223u, 1104069332u, 2844130133u, 2713773580u,  110283227u,
    2481609072u,  581450358u, 1141429464u,  573767071u,  628702638u,
    1226175933u, 1496995439u, 1105107520u, 3790323315u, 2629122303u,
    1138385203u, 2081547238u, 4128122826u,  547119985u, 1760069398u,
     341033734u, 2326900356u, 3647703883u, 3295713467u,  325211857u,
     247163411u, 3534750987u, 1351316687u, 3425408611u, 1131435045u,
      56237162u, 1182140676u, 2841516219u, 2036405666u, 3011909393u,
     181354475u, 4099399022u, 2263280522u, 3301402229u,  171474648u,
     671798090u, 1018093993u, 4168485423u, 1275944499u,  823679180u,
    4200934132u, 1111934299u, 3199618087u, 3621066247u, 3422907952u,
    1960186230u,  327155934u, 2648626799u, 3085590530u, 3118851840u,
    3791862980u, 2023795762u,    9700208u, 2361138067u, 4268467660u,
    3704256002u, 2875035367u, 2027303960u, 3457589647u,  885044336u,
    2662844726u, 3072057497u, 4210718634u, 1713969286u, 1983796584u,
     162684133u, 1680075615u, 1605451006u,  213476914u,  633139757u,
    3749313632u, 1967155290u,  256432133u,  409228965u, 3211834734u,
    2708956481u, 1130100839u, 2725640478u,  945525536u, 2527400967u,
     835878402u, 3714026506u, 3349608339u, 3265722245u,  387938828u,
    1661608822u, 1945317790u,   63762452u, 4267518590u, 2829827589u,
     803587489u, 2011172466u, 3058409291u, 2493493652u, 2358944923u,
     717080147u, 3264332285u, 4198730664u, 1575482429u,  318381561u,
     665649665u, 4090251887u,  927143108u, 2862607660u, 1760435706u,
    1877432652u, 1771873366u, 1874464602u, 1167059997u, 3020490408u,
    1074066123u, 1379644398u,  126243592u, 3195614646u,  379454934u,
    3916240656u, 2888173309u, 3691637364u, 3074570305u,  234168674u,
     984718484u, 2323634090u, 2957625706u, 3571063313u, 3046748310u,
     939117845u, 2447953439u, 3607149135u, 2109921668u, 1582617334u,
    2947121532u, 2088820125u, 1311220491u, 1306760315u, 1526878608u,
    3921204841u, 1464365659u, 4088339779u, 3839989510u, 2702193424u,
    3033074280u, 3344899646u, 2784651874u, 1276498418u, 3085361132u,
    3355531897u, 4084951190u, 1501726664u, 1175048372u,  404968257u,
    1222303786u, 1754944111u, 2544068457u, 3514209187u, 2271843748u,
    1475268510u, 3989245286u, 1371106318u,  129716112u, 3544402121u,
    4044152139u, 2679423850u, 2290541585u, 3199575633u,  744603621u,
     458754085u,  621232718u, 3523809203u, 3640321157u, 4159876693u,
    3292542003u, 2614643405u, 2265268131u, 2175536109u, 2364640379u,
    2464849350u,  788537884u,  947581145u, 1865279252u, 2550878652u,
     287140567u, 3765319030u, 3181972603u, 1037202683u,  574960613u,
     723287358u, 2264164901u, 1548449675u, 1992765225u, 1943406983u,
    4007764606u, 2734816626u, 1133263828u, 4094045449u,  330380303u,
    1351242405u, 2139587057u, 1170408100u, 2151621933u, 3076660584u,
     577955961u, 2930728868u, 2191524223u,  990695029u, 3332539164u,
    2415265923u,  402298882u, 4102255429u, 2991709119u, 2498622844u,
    4105956877u,  183958547u,  653603897u, 1809232009u, 1453424169u,
    1640850437u, 2483305045u, 3842897193u, 2820742683u,  675242394u,
     234672814u, 1219775413u, 2856515609u,  488790066u, 2475713844u,
     827998856u,  772322586u,  143954203u, 1728063401u, 2999097055u,
    1258585961u,  139439149u, 3785937564u, 4250215304u, 1921492716u,
    2854837455u, 3335291046u, 1117431624u, 1803714835u, 1365730596u,
     176474541u, 1195819223u, 1905686043u, 2606575318u,  644255847u,
    2626902930u, 1696029855u, 2469470787u, 3140744731u, 3124183743u,
     681584615u, 3124853055u,  521289913u, 3037640139u,  694512606u,
    4196362636u, 3221960124u, 1809151323u, 3104570936u, 3457186537u,
    3230064790u,  949139600u, 2794693823u, 3605652340u, 2682195244u,
    1972126161u, 1304624176u, 2917192451u, 3413390736u, 1272630300u,
    1614264576u, 3114707895u, 2828194783u, 2737493590u, 1438642720u,
     398059486u, 2046323248u, 3858845675u,  753870998u, 3263763629u,
    3560607974u,   97620978u, 2751877635u, 1508838838u, 4235953225u,
     889039423u, 2749896870u, 1058740777u,  186726216u, 1997325597u,
     673398419u, 4054809100u, 3573007303u,  864341058u, 2870750111u,
    1875827492u, 2133845783u, 1989074132u, 2286405673u, 1834455764u,
    2866334629u, 2924929701u, 1437706889u, 3399134825u, 2989971535u,
     360902372u, 1167328961u,   13923096u, 4046233402u, 4170341145u,
    1168846931u, 4262408566u, 4159192264u, 1382737528u, 1362165181u,
     134110655u, 1886221955u, 2952826762u, 3449176844u, 1662266626u,
    1122229274u, 4041152892u, 3130892823u,  598378225u, 1217727498u,
    1225176566u,  133190688u, 3323826221u,  547888910u, 1668299591u,
     504078819u, 2524882623u, 2749626450u, 2984267770u, 1427332581u,
    1374197092u, 2776391902u, 2950543940u, 3597584186u, 1694883952u,
    3690380608u, 4219862249u, 3194989758u,   45833324u, 2290428961u,
    1194523277u, 2080305090u,  727617120u, 1871861852u, 2852766462u,
    1377621335u, 4205311198u,  639785910u,  283107621u, 2955818106u,
    2342915166u,  553292194u, 1923106993u, 2037851645u, 2977117774u,
    2451042230u, 2414973112u,  684116259u, 2194888935u, 1353049451u,
    1794293340u, 2470657725u, 1586299181u, 2930169238u, 1014804130u,
    2325649911u,  129021041u, 1332147710u, 1594434776u,  674914589u,
     435079932u, 3519940708u, 2142186807u,  358685975u,  901678227u,
    2225668560u, 1990950041u, 2073465681u, 3692487862u, 1345669515u,
    4269341801u, 3287189638u,  557048773u,  975524480u, 1180641558u,
    2197478024u,  100938323u, 2993700884u, 3977138677u,  392899815u,
    1337314430u, 2115757123u, 1596565812u, 2447096231u, 1875036431u,
    2756857064u, 4245104177u, 2570394607u, 1863785892u, 2677793010u,
    1725064153u, 1458810935u, 1917847573u, 4193832098u,  643623708u,
    3495798825u,  710289455u,  761817339u, 3299308563u,  671529304u,
     230310926u, 1510576771u, 3374303917u, 1704698596u, 1640684325u,
     822663837u, 2547915455u, 4069104144u, 2430564715u, 2053841090u,
     986319080u, 2210107029u,  412064727u, 2783613259u,  279039381u,
     499244831u,   99653989u, 2628011239u, 3746387564u, 1339491367u,
    1544434309u,  582419827u,  399172998u, 2292817995u, 3518067082u,
    1978161243u, 2134178320u,   50584408u, 1639288186u, 3729935645u,
    3394981086u, 3970214462u, 2266863843u, 2098019031u, 3498932754u,
    2425450669u, 3011644541u, 2154834295u, 1566569217u, 3550818423u,
    3342256364u, 2855763981u, 3737540430u, 1191621881u, 3840446275u,
    1890042079u,  672062740u, 2015167539u, 1224827706u,  163630564u,
    1492072834u, 2802873157u, 1707472572u, 3763790259u, 1331259087u,
    1950565242u, 3384631538u, 1117904786u,  856680687u, 4110420132u,
    2624530728u, 3940769225u, 1495633832u, 3665314334u,  706218959u,
    2446541599u, 3767005930u, 1761813284u,  793760371u, 3843098778u,
    1378121808u, 2531610112u, 4281885086u,  722781736u, 3023014411u,
    2799556405u, 2819357928u, 3141278046u, 2441527005u, 4151479894u,
    1896941819u,  596201422u, 2064424897u, 2126371058u, 3296815812u,
    4010070378u,  259579352u, 2113384079u, 1090898587u, 3505987476u,
     678816428u, 1752720171u,  557092635u,  204016079u, 3300920851u,
    2972890266u, 2447503403u, 3824050309u, 1206418589u,   40226916u,
    1013674257u, 2994695015u, 2420661479u,  617755021u,  761607669u,
    1276642071u, 1207975455u,  371458107u,  526906162u, 1617712095u,
     583234254u, 3855581398u, 2661783995u, 3557719699u,  492761818u,
     633313678u, 1392788289u, 2926435278u, 3269052534u, 2927639451u,
    3355075155u, 4140349814u, 4017839768u,  273149017u, 4129597307u,
     159613376u, 2525558019u, 2853612230u, 1277913653u, 2906920607u,
     245739105u,   99670052u, 2124723003u, 1161668924u, 3249459940u,
    4027543729u,  249730846u, 2654735532u, 1775757814u, 2799175066u,
     994058658u, 3128508225u, 4060936510u, 1764669280u, 1591440959u,
    3594681350u,  824721464u,  225498530u, 2961877671u, 2164367433u,
    2227307590u, 3668888759u,  778727920u, 4021230187u, 1989921618u,
    4074077089u, 1773124827u, 1248866715u, 1571786792u, 3651230686u,
    1590808960u, 1798833201u, 3171851922u, 1907257896u,  422163767u,
     771204939u, 1569344449u, 3620107018u,  312184228u, 2667690438u,
    2736728328u, 3351679326u, 4293266120u, 1479297505u, 1321697177u,
    1476450712u, 1821458355u,  510639697u, 3353685695u, 3223862600u,
    1065307464u, 3396619366u, 2438080414u,  722925129u, 3029250790u,
    3723401561u,  325572601u, 3630972120u,  385035816u, 2107583779u,
    3204626616u,  100167064u, 3021789383u, 3958838301u,  863200373u,
    1536140033u, 1653480108u, 3275112869u, 3452491352u,  830675654u,
    1927345594u, 2721579912u, 3629599505u,  892928392u, 1071240868u,
     251251858u,  196891116u, 3491476074u,  899382703u, 3890183726u,
    3826018294u, 1017648853u,  920309298u, 3340661250u, 2612512342u,
    2811793941u, 4174781029u, 3506353467u, 2033190700u, 3373457460u,
    2339237219u, 1020418269u, 3590499880u, 3692832637u, 3566030303u,
    1832595957u, 2775942935u,   58937028u,  226274185u, 2552664048u,
     208605615u, 2633014230u, 3004371310u,  743686731u, 2417265339u,
    3267972504u, 2486843234u, 1371501517u, 1968339331u, 3795872153u,
     484975515u, 1740963751u,  890579912u,  399537152u, 3425765123u,
      36545252u, 1700278613u, 2071323863u, 2207555149u, 3425290523u,
      26019342u, 1529855572u, 2783751810u, 2802986929u, 3415140068u,
    1064923916u, 3314992217u,   85471931u, 3509335678u, 3056191779u,
    1825414916u, 1273785748u, 1884000304u, 2179774775u,  812453409u,
    3224911175u, 3058589832u, 2859786012u, 2418387021u, 3114589689u,
    2615992905u, 4042607554u,  970734203u, 3573160036u, 2692623241u,
    1997039864u,  847852728u, 2229073638u,   74712714u, 1252676139u,
    2628109988u, 2504938772u, 1379597940u, 2056368055u, 2089953286u,
    1811579802u,  415412431u, 1439907673u, 1313375505u, 4204976878u,
    1700729450u, 1039803553u, 2234612811u, 1824366910u, 2738413467u,
    2205109633u, 1250436225u, 2132231554u, 3458837279u,  598753273u,
    2368403394u, 4021049970u, 1394468059u, 1917980928u, 2513390407u,
    2845111052u,  112183242u, 2065736285u, 3374680080u, 2630858879u,
    2493197297u,  857666598u,  239366099u,  396468925u, 2165301993u,
    2566000373u, 3177083531u, 1241714532u, 4138061872u, 2894145478u,
    1129982759u, 1308535112u,  192836408u, 3902463321u,   21115860u,
    2852921750u,  133647041u, 2764366837u, 1745066212u, 4175089945u,
     626870811u, 1145341095u, 2949286171u,  875760879u, 1701610962u,
    2050177321u, 3255313724u,  579430573u, 2941018813u, 1643825778u,
    1448244108u, 1264534555u, 3064122081u, 1018367855u,   74340227u,
    2032257813u, 3231709827u, 2162359926u, 3883904895u, 1769910445u,
    2646114017u, 1568370967u, 3688753437u, 2727243902u, 2762786309u,
     736986713u, 4164267736u, 2275640205u, 3502195760u, 2422971628u,
    1314654948u,  231264130u, 2622060886u, 1428226261u, 1895991720u,
    3901143259u,   21840777u, 1626372171u, 3100053354u, 1887939103u,
     953797637u, 2090256210u, 1038111897u,  870472499u, 1782057015u,
     881883769u, 2252280146u,  539294114u, 1255572216u, 2539098155u,
    1593341126u, 3426128314u, 2067868398u, 3497890577u,  734480408u,
    3561086192u, 2482993071u,   28230985u, 3952654161u, 2386376929u,
    3187237308u, 1027326004u, 1322417976u,  674246931u, 2567828541u,
     462810786u, 3906345343u, 2679088468u, 1635438811u,  917859212u,
     397746780u, 2991343807u, 2242932293u, 3257743007u, 1536536942u,
    2310652354u, 3858234926u, 1785883731u, 4148952914u,  542852434u,
     405520301u, 1356469089u, 2662672540u, 2774250057u, 1100086288u,
    3006372138u, 1239397222u, 1008026014u, 1943675912u, 1446208466u,
    2821271137u, 2469856346u, 1735560439u,  306160955u, 1604643170u,
    2628512252u, 1464887538u, 4040683764u, 1699601332u, 2569212800u,
    3373761230u, 2970178404u,  394939247u, 1969326589u, 3641297762u,
    3552329785u, 3494204604u, 2533477003u,  839404457u, 2837066589u,
    1887770399u, 3963240603u, 1566589133u, 3277605804u, 3366293223u,
    2503723792u, 2105674080u, 2170235408u, 4130642859u, 2899266769u,
    1268252521u, 4054726046u, 1799410781u, 1691559077u, 2708694364u,
    2508525360u, 4076845476u, 1933402539u,  106704659u, 3789369987u,
    3771235034u,  520734008u, 2442493189u, 3815388346u, 2027438978u,
    1095008152u,  590458232u,   98793519u, 1146786523u,  156665803u,
    2792356386u, 2047668331u, 1210331595u, 2616724516u, 1009701537u,
     697639289u, 1367514263u, 1077777630u, 3172655958u, 3111472002u,
    3943877061u, 3567041390u, 1507343754u, 1349917753u, 2183327131u,
    1308313591u, 1986589932u, 2085617066u, 4009147247u, 2968668381u,
    3551135214u,  892982226u,  862813360u, 3985060019u, 1376926050u,
    3024188003u,  949735999u, 2871900054u, 3171468848u,  576549665u,
    2823667892u,  988046782u, 2391409204u, 1713668465u, 1020006796u,
    2118242357u, 2201459024u, 1317303980u, 1749974557u,  632277769u,
    3688223773u, 3145962284u,  262063403u, 2139143645u, 3099046811u,
    2787373021u,  529996562u, 1510774569u, 1310986691u, 1510343925u,
    1536308645u, 2630193557u, 1953926582u, 2246912376u, 3768067684u,
     300316896u, 1802303731u, 1270975835u, 3884467171u,  497161489u,
    2097346700u,   14945728u, 2290965917u, 3689541248u, 3254637316u,
    3907317116u, 2862282616u, 4040733349u,   37537367u, 2387383048u,
     395862630u, 2778708620u, 3411960647u, 2656086542u, 1787782087u,
    4270883693u,  649699601u, 1274984918u, 3247080139u, 2726606914u,
     101994024u, 2381680152u, 2496887912u, 1438931885u, 1972814463u,
    3304990985u, 1411408562u, 3639691527u, 2127645603u, 1249273999u,
    4042725697u, 3194015825u, 4004654193u,  564908550u, 2868688439u,
    2039450632u, 1332535630u, 2602944856u, 1924842299u,  971814105u,
     834403437u, 3193316525u, 1644914174u,  863939595u, 4014965922u,
    3805794715u,  634057055u, 3608454301u, 3289222059u,  620808484u,
    2329157819u, 1684810552u, 3258379622u, 1645866960u, 2399432486u,
    3343530218u, 4263505887u,  722741832u, 3800010203u,  658988677u,
    1484073050u, 3101531846u, 3874976772u, 4206597126u, 1848102857u,
    3193138690u,  983512797u,  391404518u, 4027880681u, 1963064961u,
    };

int main(int argc, char* argv[])
    {
    volatile double	dummy_double;
    volatile unsigned long
			dummy_long;
    volatile unsigned long long
			dummy_longlong;
    mt_prng		rng;
    static long		timing_loops = TIMING_LOOPS;

    /*
     * If the user has given a number of timing loops, reset the loop count.
     */
    if (argc > 1)
	timing_loops = atol(argv[1]) * TIMING_LOOP_BASE;

    /*
     * Compare the generated values against corresponding numbers from
     * Matsumoto and Nishimura's own generator, to make sure we're
     * doing the calculation correctly.
     */
    cout << "Validity test...";
    rng.seed32(4357);
    ofstream save("mtccsave");
    save << rng << '\n';
    save.close();
    rng.seed32(1);
    ifstream restore("mtccsave");
    restore >> rng;
    restore.close();
    unlink("mtccsave");
    for (unsigned long i = 0;
      i < sizeof correct_values / sizeof correct_values[0];
      i++)
	{
	unsigned long random_value = rng.lrand();
	if (random_value != correct_values[i])
	    {
	    cerr << "Failure at value " << i << ": expected "
	      << correct_values[i] << ", got " << random_value << '\n';
	    return 1;
	    }
	}
    cout << "passed.\n";

    /*
     * Timing tests.
     */
    struct rusage	then;
    cout << timing_loops << " longs took        ";
    getrusage(RUSAGE_SELF, &then);
    unsigned long random_value = 0;
    for (long i = 0;  i < timing_loops;  i++)
	random_value += rng.lrand();
    report_timing(timing_loops, &then);
    dummy_long = random_value;

    unsigned long long longlong_value = 0;
    cout << timing_loops << " long longs took   ";
    getrusage(RUSAGE_SELF, &then);
    for (long i = 0;  i < timing_loops;  i++)
	longlong_value += rng.llrand();
    report_timing(timing_loops, &then);
    dummy_longlong = longlong_value;

    double double_value = 0.0;
    cout << timing_loops << " fast doubles took ";
    getrusage(RUSAGE_SELF, &then);
    for (long i = 0;  i < timing_loops;  i++)
	double_value += rng.drand();
    report_timing(timing_loops, &then);

    cout << timing_loops << " long doubles took ";
    getrusage(RUSAGE_SELF, &then);
    for (long i = 0;  i < timing_loops;  i++)
	double_value += rng.ldrand();
    report_timing(timing_loops, &then);

    cout << timing_loops << " call doubles took ";
    getrusage(RUSAGE_SELF, &then);
    for (long i = 0;  i < timing_loops;  i++)
	double_value += rng();
    report_timing(timing_loops, &then);

    dummy_double = double_value;

    return 0;
    }

static void report_timing(
    long		loops,		/* Number of loops that were done */
    struct rusage *	then)		/* Time test started */
    {
    long		diff;		/* Difference in times */
    long		microdiff;	/* Microsecond part of difference */
    struct rusage	now;		/* Time test ended */
    double		secs;		/* Actual seconds needed */

    getrusage(RUSAGE_SELF, &now);
    diff = now.ru_utime.tv_sec - then->ru_utime.tv_sec;
    microdiff = now.ru_utime.tv_usec - then->ru_utime.tv_usec;
    if (microdiff < 0)
	{
	diff--;
	microdiff += 1000000;
	}
    secs = diff + (microdiff / 1000000.0);
    cout << setw(3) << diff << "." << setw(6) << setprecision(6) << microdiff;
    cout << setw(0) << setprecision(0) << " seconds (" << (long)(loops / secs)
      << "/sec).\n";
    }
